前言

大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
那就開始今天的解題吧~

Question

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

Note that division between two integers should truncate toward zero.

It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

Example 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Constraints:

• 1 <= tokens.length <= 10^4
• tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

Think

逆波蘭表示法（Reverse Polish notation，RPN，或逆波蘭記法），是一種是由波蘭數學家揚·武卡謝維奇1920年引入的數學表達式形式，在逆波蘭記法中，所有操作符置於操作數的後面，因此也被稱為後綴表示法、後序表示法。 逆波蘭記法不需要括號來標識操作符的優先級

給一個tokens的陣列，裏頭存有數字或運算符號，要回傳這個RPN式子的運算值。

我們要用一個stack來存這個RPN中的數字字串，然後遇到運算符號就把stack中最後丟進去的兩個數拿出來運算(順序很重要!)，然後再把算完的值丟回stack，重複這個動作~

在寫這題的時候，遇到的問題是除法除完如果是分數怎麼辦?!
- 看了Example 3才發現，除完小數的部分會被捨棄，所以除法的部分，我們直接把值轉int就好~

Code

#include <string>
#include <vector>

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        
        vector<long> stack;
        
        for(int index=0 ; index<tokens.size() ; index++){
//             if(tokens[index] == "+"){
                
//                 cout << tokens[index] << endl;
//             }
            if(tokens[index] == "+"){
                long num1 = stack[stack.size()-1];
                stack.pop_back();
                long num2 = stack[stack.size()-1];
                stack.pop_back();
                stack.push_back(num1 + num2);
                // cout << num1 + num2 << endl;
                                
            } else if(tokens[index] == "-"){
                long num1 = stack[stack.size()-1];
                stack.pop_back();
                long num2 = stack[stack.size()-1];
                stack.pop_back();
                stack.push_back(num2 - num1);
                
            } else if(tokens[index] == "*"){
                long num1 = stack[stack.size()-1];
                stack.pop_back();
                long num2 = stack[stack.size()-1];
                stack.pop_back();
                stack.push_back(num1 * num2);
                    
            } else if(tokens[index] == "/"){
                long num1 = stack[stack.size()-1];
                stack.pop_back();
                long num2 = stack[stack.size()-1];
                stack.pop_back();
                stack.push_back(static_cast<long>(num2 / num1));
                
            } else {
                stack.push_back(std::stoi(tokens[index]));
                // cout << stack[index] << endl;
            }
        }
        
        
        return stack[0];
    }
};

Submission

今天就到這邊啦~
大家明天見